\subsubsection{Übung (vi) - \buchmann{16.3.2}}

\paragraph{Aufgabe:}
Sei $n = 4, t = 2, p = 11, s = 3$, $a_{1} = 2$. Konstruieren Sie $a(X)$ und die Geheimnisanteile $y_{i} , 1\leq i \leq 4$. 

\paragraph{Lösung:}

\textbf{Berechnung der Geheimnisanteile:}\\
Das Geheimnis $s$ und der erste Koeffizient des Ploynoms $a_{1}$ sind bereits gegeben. Da $t-1 = 2-1 = 1$ gilt, ist das Polynom eine Gerade und vom Grad eins. Es müssen keine weiteren Koeffizienten zufällig gewählt werden. Für das Polynom $a(X)$ gilt daher:

\[
a(0) = s + \sum_{j=1}^{t-1} a_{j} * X^j = s + \sum_{j=1}^{1} a_{1} * X = 3 + 2X
\]

Für $x_{i}, 1 \leq i \leq 5$ werden die Werte $x_{1} = 2, x_{2} = 3, x_{3} = 2$ und $x_{4} = 5$ gewählt. Für $y_{i}$ werden folgende Werte berechnet:
\[
y_{1} = a(x_{1}) = a(2) = (3 + 2 * 2)\mod 11 = 7 
\]
\[
y_{2} = a(x_{2}) = a(3) = (3 + 2 * 3)\mod 11 = 9 
\]
\[
y_{3} = a(x_{3}) = a(4) = (3 + 2 * 4)\mod 11 = 0 
\]
\[
y_{4} = a(x_{4}) = a(5) = (3 + 2 * 5)\mod 11 = 2 
\]
\\
\textbf{Rekonstruktion der Geheimnisanteile:}\\
Das $s$ kann aus nun von zwei Geheimnisträgern wieder rekonstruiert werden. Beispiel $y_{1}$ und $y_{2}$. Dazu werden wie in Übung (v) die Produkte $L_i(0) = \prod_{j \ne i}^t \frac{x_j}{x_j - x_i}$ berechnet und anschließend gemeinsam mit den $y_{i}$ in das Lagrange-Interpolationspolynom eingesetzt.
\begin{center}
\[
L_{2}(0) = \frac{x_{3}}{x_{3} - x_{2}} = \frac{3}{3 - 2} = \frac{3}{1} 
\]
\[
L_{3}(0) = \frac{x_{2}}{x_{2} - x_{3}} = \frac{2}{2 - 3} = \frac{2}{-1} 
\]
\end{center}
Eingesetzt in $a(0)$ ergibt:
\begin{center}
\[
a(X) = (\frac{3}{1} * 7 + \frac{2}{-1} * 9)\mod 11
\]
\[
a(X) = (21 - 18) = 3 \equiv 3\mod 11
\]
\end{center}
Das Geheimnis konnte also durch beliebige $t$ Geheimnisträger rekonstruiert werden.